package recursion.dp;

public class LengthOfLongestPSubseq {
    public static String longestPalindromeSubseq(String s) {
        String[][] dp = new String[s.length()][s.length()];
        return LPSRecur(s, 0, s.length() - 1, dp);
    }

    public static String LPSRecur(String s, int startIdx, int endIndx, String[][] dp) {
        if (startIdx > endIndx)
            return "";
        if (startIdx == endIndx)
            return String.valueOf(s.charAt(startIdx));
        //if memo array haven't got the ans for the sub problem, then we need to compute the ans
        if (dp[startIdx][endIndx] == null) {
            //case 1 tail char equals head char
            if (s.charAt(startIdx) == s.charAt(endIndx))
                dp[startIdx][endIndx] = s.charAt(startIdx) + LPSRecur(s, startIdx + 1, endIndx - 1, dp) + s.charAt(startIdx);
            else {
                //case 2 tail char not equals head char
                String s1 = LPSRecur(s, startIdx + 1, endIndx, dp);
                String s2 = LPSRecur(s, startIdx, endIndx - 1, dp);
                dp[startIdx][endIndx] = s1.length() > s2.length() ? s1 : s2;
            }
        }
        //if the answer has been computed already, we just use it directly
        return dp[startIdx][endIndx];
    }

    public static void main(String[] args) {
        String testStr = "abbfesbccbbbdaefdjhjghjgdytfhjmgjkhlih" + 'c';
        System.out.println(longestPalindromeSubseq(testStr));
    }
// todo figure out how to return the exact pad subseq
}
